#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}
ll inv(ll a,ll m){
    ll x,y;
    ll d=exgcd(a,m,x,y);
    if(d==1){
        return (x%m+m)%m;
    }
    return -1;
}
ll n,b;
int t;
const ll MOD=9973;
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&b);
        ll c=inv(b,MOD);
        printf("%lld\n",n*c%MOD);
    }
    return 0;
}